Basic review of set, subset, partition, equivalence relation.
A partition of a set is a surjective map to the parts.
Any \(a \in A\) can be thought of as a function \(\{1\} \xrightarrow{a} A\)
Suppose \(A\) is a partitioned set and \(P,Q\) are two partitions such that for each \(p \in P\) there exists a \(q \in Q\) with \(A_p=A_q\)
Show that for each \(p \in P\) there is at most one \(q \in Q\) such that \(A_p = A_q\)
Show that for each \(q \in Q\) there is a \(p \in P\) such that \(A_p = A_q\)
Suppose \(q' \ne q\). If they are both equal to \(A_p\) then they are equal to each other, but a partition rule is that \(q' \ne q\) must have an empty intersection (and \(A_p\) cannot be empty by the other rule).
By part 1, the mapping between part labels is a bijection, so there is an inverse map as well.
Finish proof Proposition 1.19. Suppose that \(\sim\) is an equivalence relation on a set A, and let P be the set of \(\sim\)-closed and \(\sim\)-connected subsets.
Show that each part \(A_p\) is nonempty
Show that \(p \ne q \implies A_p \cap A_q = \varnothing\)
Show that \(A = \bigcup_{p \in P} A_p\)
Part of the definition of \(\sim\)-connected is being nonempty
Suppose \(a \in A\) is in the intersection. Then \(a \sim p\) and \(a \sim q\) for some elements \(p \not\sim q\) arbitrarily selected from \(A_p, A_q\). But this is impossible because \(\sim\) is transitive, so this must be impossible.
Every \(a \in A\) is part of some equivalence class which is a \(\sim\)-closed and \(\sim\)-connected set, so \(A \subseteq \bigcup_{p \in P} A_p\)
The equivalence class is \(\sim\)-closed because two elements being \(\sim\)-related implies they are in the same equivalence class.
The equivalence class is \(\sim\)-connected because equivalence classes are nonempty and the equivalence relation is transitive.
The constituents of \(A_p\) were defined to be subsets of \(A\), so unioning these will also be a subset of \(A\), i.e. \(\bigcup_{p \in P} A_p \subseteq A\).
Therefore \(A = \bigcup_{p \in P} A_p\).
A function from \(S\) to \(T\)
A relation \(F \subseteq S \times T\) such that \(\forall s \in S:\ \exists! t \in T:\ (s,t) \in F\)
The preimage of an element \(t \in T\) is \(\{s \in S\ |\ F(s)=t\}\)
\(\hookrightarrow\) Injectivity: \(s\ne s' \implies F(s)\ne F(s')\)
\(\twoheadrightarrow\) Surjectivity: \(\forall t \in T:\ \exists s \in S:\ (s,t) \in F\)
\(\xrightarrow \cong\) Bijectivity: both injectivity and surjectivity.
A partition of set \(A\)
A set \(P\) (‘part labels’) and, for each \(p \in P\), a nonempty subset (‘pth part’) \(A_p \subseteq A\) such that:
\(A = \bigcup_{p \in P}A_p\)
\(p \ne q \implies A_p \cap A_q = \varnothing\)
Two partitions are considered the same if the partitioned groups are the same, the labels don’t matter.
There is a bijection between ways to partition a set \(A\) and the equivalence relations on \(A\)
Every partition gives rise to a distinct equivalence relation
Define \(a \sim b\) to mean \(a,b\) are in the same part. This is a reflective, symmetric, and transitive relation given the definition of a partition.
Every equivalence relation gives rise to a distinct partition.
Define a subset \(X \subseteq A\) as \(\sim\)-closed if, for every \(x \in X\) and \(x' \sim x\), we have \(x' \in X\).
Define a subset \(X \subseteq A\) as \(\sim\)-connected if it is nonempty and \(\forall x,y \in X:\ x \sim y\)
The parts corresponding to \(\sim\) are precisely the \(\sim\)-closed and \(\sim\)-connected subsets.
A quotient of a set under an equivalence relation.
This is equivalent to the parts of the partition associated with the equivalence relation.
A relation between sets \(X\) and \(Y\)
A subset \(R \subseteq X \times Y\).
A binary relation on \(X\) is a subset of \(X \times X\)